{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Divisible Subset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestDivisibleSubset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大整除子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个由 <strong>无重复</strong> 正整数组成的集合 <code>nums</code> ，请你找出并返回其中最大的整除子集 <code>answer</code> ，子集中每一元素对 <code>(answer[i], answer[j])</code> 都应当满足：\n",
    "<ul>\n",
    "\t<li><code>answer[i] % answer[j] == 0</code> ，或</li>\n",
    "\t<li><code>answer[j] % answer[i] == 0</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>如果存在多个有效解子集，返回其中任何一个均可。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[1,2]\n",
    "<strong>解释：</strong>[1,3] 也会被视为正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,4,8]\n",
    "<strong>输出：</strong>[1,2,4,8]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 1000</code></li>\n",
    "\t<li><code>1 <= nums[i] <= 2 * 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-divisible-subset](https://leetcode.cn/problems/largest-divisible-subset/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-divisible-subset](https://leetcode.cn/problems/largest-divisible-subset/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[1,2,4,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        rec = {}\n",
    "        for x in nums:\n",
    "            rec[x] = max([[]] + [rec[k] for k in rec if x % k == 0], key = len) + [x]\n",
    "        return max(rec.values(), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return []\n",
    "        \n",
    "        nums.sort()\n",
    "        \n",
    "        dp=[1 for i in range(len(nums))]\n",
    "        \n",
    "        dp[0]=1\n",
    "        \n",
    "        length,index,res=0,0,[]\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[i]%nums[j]==0:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "                    if dp[i]>length:\n",
    "                        length=dp[i]\n",
    "                        index=i\n",
    "        \n",
    "        temp,curdp=nums[index],dp[index]\n",
    "        for i in range(index,-1,-1):\n",
    "            if temp%nums[i]==0 and dp[i]==curdp:\n",
    "                res.append(nums[i])\n",
    "                temp=nums[i]\n",
    "                curdp-=1\n",
    "                \n",
    "        return res\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#coding=gbk\n",
    "class Solution(object):\n",
    "\tdef largestDivisibleSubset(self, nums):\n",
    "\t\tif not nums:return []\n",
    "\t\t#若先进行排序，而后动态规划\n",
    "\t\tnums.sort()\n",
    "\t\tdict1={nums[0]:[nums[0]]}\n",
    "\t\tfor i in range(1,len(nums)):\n",
    "\t\t\tdict1[nums[i]]=[nums[i]]\n",
    "\t\t\tfor j in range(i):\n",
    "\t\t\t\tif nums[i]%nums[j]==0 and len(dict1[nums[j]])+1>len(dict1[nums[i]]):\n",
    "\t\t\t\t\tdict1[nums[i]]=dict1[nums[j]]+[nums[i]]\n",
    "\t\tlength=0\n",
    "\t\tre=[]\n",
    "\t\tfor ll in dict1.values():\n",
    "\t\t\tif len(ll)>length:\n",
    "\t\t\t\tre=ll\n",
    "\t\t\t\tlength=len(ll)\n",
    "\t\treturn re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return []\n",
    "        nums = sorted(nums)\n",
    "        def canputin(a_set, newer):\n",
    "            elem = max(a_set)\n",
    "            if not(newer%elem == 0):\n",
    "                return False\n",
    "            return True\n",
    "        maxsets = []\n",
    "        for num in nums:\n",
    "            maxset = {num}\n",
    "            for pastnum, pastmaxset in zip(nums, maxsets):\n",
    "                if len(pastmaxset)+1>len(maxset) and num%pastnum == 0:\n",
    "                    maxset = pastmaxset|{num}\n",
    "            maxsets.append(maxset)\n",
    "        return list(max(maxsets, key=len))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        nums.sort()\n",
    "        res = [[nums.pop(0)]]\n",
    "        for i in nums:\n",
    "            flag = True\n",
    "            res.sort(key=len,reverse=True)\n",
    "            for j in res[:]:\n",
    "                if not i%j[-1]:\n",
    "                    res.append(j+[i])\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append([i])\n",
    "        res.sort(key=len,reverse=True)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(nums) is 0:\n",
    "            return []\n",
    "        nums = sorted(nums)\n",
    "        dp_set = [[nums[0]]]\n",
    "        for i in range(1,len(nums)):\n",
    "            div = [False for _ in range(i)]\n",
    "            last_div = None\n",
    "            for j in range(i):\n",
    "                if nums[i]%nums[j]==0:\n",
    "                    div[j]=True\n",
    "            for k in range(i):\n",
    "                if div[k] is True:\n",
    "                    if last_div is None:\n",
    "                        last_div = k\n",
    "                    else:\n",
    "                        if len(dp_set[k])>len(dp_set[last_div]):\n",
    "                            last_div = k\n",
    "            if last_div is None:\n",
    "                dp_set.append([nums[i]])\n",
    "            else:\n",
    "                new_set = dp_set[last_div] + [nums[i]]\n",
    "                dp_set.append(new_set)\n",
    "        \n",
    "        max_index = dp_set.index(max(dp_set,key=len))\n",
    "        \n",
    "        return dp_set[max_index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(nums) is 0:\n",
    "            return []\n",
    "        nums = sorted(nums)\n",
    "        dp_set = [[nums[0]]]\n",
    "        for i in range(1,len(nums)):\n",
    "            div = [False for _ in range(i)]\n",
    "            last_div = None\n",
    "            for j in range(i):\n",
    "                if nums[i]%nums[j]==0:\n",
    "                    div[j] = True\n",
    "            for k in range(i):\n",
    "                if div[k] is True:\n",
    "                    if last_div is None:\n",
    "                        last_div = k\n",
    "                    else:\n",
    "                        if len(dp_set[k])>len(dp_set[last_div]):\n",
    "                            last_div = k\n",
    "            if last_div is not None:\n",
    "                new_set = dp_set[last_div] + [nums[i]]\n",
    "                dp_set.append(new_set)\n",
    "            else:\n",
    "                dp_set.append([nums[i]])\n",
    "        max_ind = dp_set.index(max(dp_set,key=len))\n",
    "        return dp_set[max_ind]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 关系不具有传递性 无法用查并集\n",
    "        # step1 排序 \n",
    "        # DP算法找到最长集合长度 以及他的最大值的位置 nums中该值位置等于DP中第一个最大值位置\n",
    "                \n",
    "        r = []\n",
    "        if not nums:\n",
    "            return r\n",
    "        \n",
    "        nums.sort()\n",
    "        dp = [1] * len(nums)\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        print(dp)\n",
    "        max_id = dp.index(max(dp))\n",
    "        max_num = nums[max_id]\n",
    "        cur_dp = max(dp)\n",
    "\n",
    "        for i in range(max_id, -1, -1):\n",
    "            print(i, dp[i], cur_dp)\n",
    "            if max_num % nums[i] == 0 and dp[i] == cur_dp:\n",
    "                r.append(nums[i])\n",
    "                cur_dp -= 1\n",
    "                print(cur_dp)\n",
    "\n",
    "        return r[::-1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        d = {}\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            temp = [num]\n",
    "            for k in d.keys():\n",
    "                if num%k==0 and len(d[k])>=len(temp):\n",
    "                    temp = d[k]+[num]\n",
    "            d[num] = temp\n",
    "        return max(d.values(),key=len)\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # if not nums:\n",
    "        #     return []\n",
    "        # nums.sort()\n",
    "        # lookup = {}\n",
    "        # for num in nums:\n",
    "        #     t = [num]\n",
    "        #     for k in lookup:\n",
    "        #         if num % k == 0 and len(lookup[k])  >= len(t):\n",
    "        #             t = lookup[k] + [num]\n",
    "        #     lookup[num] = t\n",
    "        # return max(lookup.values(), key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        dp = [[x] for x in nums]\n",
    "        maxseq = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[i]%nums[j] == 0 and len(dp[j])+1>len(dp[i]):\n",
    "                    dp[i]  = dp[j]+nums[i:i+1]  # 写 nums[i]会报错\n",
    "            if len(dp[i])>len(maxseq):\n",
    "                maxseq = dp[i]\n",
    "        return maxseq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n==0:\n",
    "            return []\n",
    "        dp=[[nums[0]]]*n\n",
    "        f= lambda x,y:x if len(x)>len(y) else y\n",
    "        for i in range(1,n):\n",
    "            cur = []\n",
    "            for j in range(i):\n",
    "                if nums[i]%dp[j][-1]==0:\n",
    "                    cur = f(dp[j],cur)\n",
    "            dp[i] = cur+[nums[i]]\n",
    "        cur = dp[0]\n",
    "        for i in range(1,n):\n",
    "            cur = f(cur,dp[i])\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums):\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        dp = [(1, N) for i in range(N+1)]\n",
    "        dp[N] = (0, 0)\n",
    "        best = (0, N)\n",
    "        for i in range(N-1, -1, -1):\n",
    "            for j in range(i+1, N):\n",
    "                if nums[j] % nums[i] == 0 and dp[j][0]+1 > dp[i][0]:\n",
    "                    dp[i] = (dp[j][0]+1, j)\n",
    "            if dp[i] > best:\n",
    "                best = (dp[i][0], i)\n",
    "        \n",
    "        res = []\n",
    "        idx = best[1]\n",
    "        while dp[idx][0]:\n",
    "            res.append(nums[idx])\n",
    "            idx = dp[idx][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        nums.sort()\n",
    "\n",
    "        dp = [1] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            maxsize = 1\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    maxsize = max(dp[j] + 1, maxsize)\n",
    "            dp[i] = maxsize\n",
    "        m = max(dp)\n",
    "        max_index = dp.index(m)\n",
    "        x = nums[max_index]\n",
    "        ans = []\n",
    "        for i in range(max_index, -1, -1):\n",
    "            if x % nums[i] == 0 and dp[i] == m:\n",
    "                m -= 1\n",
    "                ans.append(nums[i])\n",
    "                x = nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        if len(nums) < 2:\n",
    "            return nums\n",
    "        max_length = 1\n",
    "        max_begin = 0\n",
    "        n = len(nums)\n",
    "        # dp[i] 为以i索引元素为最后一个元素的最长子数组\n",
    "        dp = []\n",
    "        max_coll = [nums[0]]\n",
    "        for i in range(n):\n",
    "            dp.append([nums[i]])\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    if len(dp[j]) + 1 > len(dp[i]):\n",
    "                        dp[i] = dp[j] + [nums[i]]\n",
    "            if len(dp[i]) > len(max_coll):\n",
    "                max_coll = dp[i]\n",
    "        return max_coll\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        dp = [[x] for x in nums]\n",
    "        maxSequence = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0 and len(dp[j]) + 1 >  len(dp[i]):\n",
    "                    dp[i] = dp[j] + nums[i : i + 1]\n",
    "            if len(dp[i]) > len(maxSequence):\n",
    "                maxSequence = dp[i].copy()\n",
    "        return maxSequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        dic = {}\n",
    "        nums.sort()\n",
    "        dp = [1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]] = [nums[i]]\n",
    "        for i in range(1, len(nums)):\n",
    "            index = i-1\n",
    "            while index >= 0:\n",
    "                if nums[i] % nums[index] == 0:\n",
    "                    if dp[i] < dp[index] + 1:\n",
    "                        dp[i] = dp[index]+1\n",
    "                        dic[nums[i]] = dic[nums[index]]+ [nums[i]]\n",
    "                index -= 1\n",
    "        dic = sorted(dic.items(), key = lambda x:-len(x[1]))\n",
    "        return dic[0][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        idxAry = [0 for _ in range(len(nums))]\n",
    "        lenAry = [i for i in range(len(nums), 0, -1)]\n",
    "        nums.append(0)\n",
    "        lenAry.append(0)\n",
    "\n",
    "        optAry = []\n",
    "        def dfs(idx, l) -> int:\n",
    "            nonlocal idxAry, lenAry, optAry\n",
    "\n",
    "            maxL = l\n",
    "            for i in range(idx+1, len(nums)):\n",
    "                if nums[i] == 0 or nums[i]%nums[idx] != 0:\n",
    "                    if l <= len(optAry):\n",
    "                        maxL = max(maxL, l)\n",
    "                        continue\n",
    "\n",
    "                    optAry = []\n",
    "                    for i in range(0, l): optAry.append(nums[idxAry[i]])\n",
    "                    continue\n",
    "                elif l + lenAry[i] <= len(optAry):\n",
    "                    maxL = max(maxL, l + lenAry[i])\n",
    "                    continue\n",
    "                    \n",
    "                idxAry[l] = i\n",
    "                maxL = max(maxL, dfs(i, l+1))\n",
    "            return maxL\n",
    "        \n",
    "        for i in range(len(nums)-1)[::-1]:\n",
    "            idxAry[0] = i\n",
    "            lenAry[i] = dfs(i, 1)\n",
    "        return optAry"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        定义：[A[0],A[1],....A[n]]为一个最大整除子集\n",
    "        如果有x%A[n]==0,那么[A[0],A[1],....A[n],x]也为整除子集\n",
    "        \"\"\"\n",
    "        from copy import deepcopy\n",
    "        n=len(nums)\n",
    "        if n<2:return nums\n",
    "        nums.sort()\n",
    "        from collections import defaultdict\n",
    "        dp=defaultdict(list)\n",
    "        # dp[nums[0]].append([nums[0]])\n",
    "        # print(dp)\n",
    "        max_len=1\n",
    "        ans=[nums[0]]\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if nums[i]%nums[j]==0:\n",
    "                    if nums[j] not in dp:\n",
    "                        dp[nums[j]].append([nums[j]])\n",
    "                    max_len_list=sorted(dp[nums[j]],key=lambda x:len(x),reverse=True)\n",
    "                    tmp=deepcopy(max_len_list[0])\n",
    "                    tmp.append(nums[i])\n",
    "                    if len(tmp)>max_len:\n",
    "                        max_len=len(tmp)\n",
    "                        ans=tmp\n",
    "                    dp[nums[i]].append(tmp)\n",
    "                     \n",
    "        print(dp)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "                \n",
    "    \n",
    "                        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        f, g = [0] * n, [0] * n\n",
    "        for i in range(n):\n",
    "            length, prev = 1, i\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0 and f[j] + 1 > length:\n",
    "                    length = f[j] + 1\n",
    "                    prev = j\n",
    "            f[i], g[i] = length, prev\n",
    "\n",
    "        max_len = -1\n",
    "        for i in range(n):\n",
    "            if f[i] > max_len:\n",
    "                max_len = f[i]\n",
    "                idx = i\n",
    "        ans = []\n",
    "        while len(ans) < max_len:\n",
    "            ans.append(nums[idx])\n",
    "            idx = g[idx]\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        prev = [-1] * n\n",
    "        dp = [1] * n\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j]==0:\n",
    "                    if dp[i] < dp[j] + 1:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        prev[i] = j\n",
    "        max_idx = dp.index(max(dp))\n",
    "        # for i in range(len(dp)):\n",
    "        #     if dp[i] > dp[max_idx]:\n",
    "        #         max_idx = i\n",
    "        while max_idx != -1:\n",
    "            res.append(nums[max_idx])\n",
    "            max_idx = prev[max_idx]\n",
    "        return res[::-1]\n",
    "            \n",
    "\"\"\"\n",
    "\n",
    "[5,9,18,54,90,180,360,108,540,720]\n",
    "\n",
    "\n",
    "[9,18,90,180,360,720]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "dp[i] record largest subset size to i \n",
    "\n",
    "\n",
    "for j=0 to i -1\n",
    "    if the nums[i] divisible iwth nums[j] then \n",
    "        if dp[i] <= dp[j] + 1\n",
    "            update dp[i]\n",
    "            and record where prev[i] = j    \n",
    "find the max dp idx and reverse the prev\n",
    "\n",
    "\n",
    "[1,2,3]\n",
    "     i\n",
    "j \n",
    " \n",
    "dp = [1,2,2]\n",
    "prev [-1,0,-1]\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        max_val = 1\n",
    "        max_size = 1\n",
    "        for i in range(1, n):\n",
    "            for j, v in enumerate(nums[:i]):\n",
    "                if nums[i] % v == 0:\n",
    "                    dp[i] = max(dp[i], dp[j]+1)\n",
    "            if max_size < dp[i]:\n",
    "                max_size = dp[i]\n",
    "                max_val = nums[i]\n",
    "\n",
    "        if max_size == 1:\n",
    "            return [nums[0]]\n",
    "\n",
    "        res = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if max_size < 0:\n",
    "                break\n",
    "            if max_size == dp[i] and max_val % nums[i] == 0:\n",
    "                res.append(nums[i])\n",
    "                max_val = nums[i]\n",
    "                max_size -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        # 子集 [a, b, c, d] 满足, 且 a < b < c < d\n",
    "        # 1.若 x > d and x % d == 0 ==> 子集 [a, b, c, d, x] 也满足\n",
    "        # 2.若 x < a and a % x == 0 ==> 子集 [x, a, b, c, d] 也满足\n",
    "        nums.sort()  # 排序后只剩下第 1 种情况\n",
    "        dp = [1] * len(nums)  # dp[i] 表示在输入数组升序排列的前提下，以 nums[i] 为最大整数的「整除子集」的大小\n",
    "        path = [-1] * len(nums)\n",
    "        end = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                if num % nums[j] == 0 and dp[j] + 1 > dp[i]:\n",
    "                    dp[i] = dp[j] + 1\n",
    "                    path[i] = j\n",
    "                if dp[i] > dp[end]:\n",
    "                    end = i\n",
    "        ans = []\n",
    "        while end != -1:\n",
    "            ans.append(nums[end])\n",
    "            end = path[end]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        dp = [[] for _ in range(len(nums))]\n",
    "        dp[0].append(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if nums[i] % nums[j] == 0 and len(dp[j]) > len(dp[i]):\n",
    "                    dp[i] = dp[j][:]\n",
    "            dp[i].append(nums[i])\n",
    "        res = dp[0]\n",
    "        for lis in dp:\n",
    "            if len(lis) > len(res):\n",
    "                res = lis\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dp = [[] for _ in range(n)]\n",
    "        print(dp)\n",
    "        nums.sort()\n",
    "        dp[0].append(nums[0])\n",
    "        for i in range(1, n):\n",
    "            maxSublen = 0\n",
    "            index = -1\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0 and len(dp[j]) > maxSublen:\n",
    "                    maxSublen = len(dp[j])\n",
    "                    index = j\n",
    "            if index != -1:\n",
    "                dp[i].extend(dp[index])\n",
    "            dp[i].append(nums[i])\n",
    "            print(dp[i])\n",
    "        print(dp)\n",
    "        return max(dp, key=len)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        # dp[i]=能被nums[i]整除的最大个数\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, i):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        \n",
    "        # print(dp)\n",
    "        max_cnt, max_div_num = 1, 0\n",
    "        for i in range(n):\n",
    "            if dp[i] >= max_cnt:\n",
    "                max_cnt = dp[i]\n",
    "                max_div_num = nums[i]\n",
    "        \n",
    "        ans = []\n",
    "    \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if max_div_num % nums[i] == 0 and dp[i] == max_cnt:\n",
    "                ans.append(nums[i])\n",
    "                max_div_num = nums[i]\n",
    "                max_cnt -= 1\n",
    "            if max_cnt == 0: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        f, g = [0] * n, [0] * n\n",
    "        for i in range(n):\n",
    "            # 至少包含自身一个数，因此起始长度为 1，由自身转移而来\n",
    "            length, prev = 1, i\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    # 如果能接在更长的序列后面，则更新「最大长度」&「从何转移而来」\n",
    "                    if f[j] + 1 > length:\n",
    "                        length = f[j] + 1\n",
    "                        prev = j\n",
    "            # 记录「最终长度」&「从何转移而来」\n",
    "            f[i] = length\n",
    "            g[i] = prev\n",
    "\n",
    "        # 遍历所有的 f[i]，取得「最大长度」和「对应下标」\n",
    "        max_len = idx = -1\n",
    "        for i in range(n):\n",
    "            if f[i] > max_len:\n",
    "                idx = i\n",
    "                max_len = f[i]\n",
    "        \n",
    "        # 使用 g[] 数组回溯出具体方案\n",
    "        ans = []\n",
    "        while len(ans) < max_len:\n",
    "            ans.append(nums[idx])\n",
    "            idx = g[idx]\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        dp=[1]*len(nums)\n",
    "        maxSize=1\n",
    "        maxVal=dp[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[i]%nums[j]==0:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "            if dp[i]>maxSize:\n",
    "                maxSize=dp[i]\n",
    "                maxVal=nums[i]\n",
    "        res=[]\n",
    "        if maxSize==1:\n",
    "            res.append(nums[0])\n",
    "            return res\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if dp[i]==maxSize and maxVal%nums[i]==0 and maxSize>0:\n",
    "                res.append(nums[i])\n",
    "                maxVal=nums[i]\n",
    "                maxSize-=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        dp = [ 1 ] * N\n",
    "        f = [ [ nums[i] ] for i in range(N) ]\n",
    "        ans = 0\n",
    "        ret = []\n",
    "        for i, a in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        f[i] = f[j] + [ nums[i] ]\n",
    "            if dp[i] > ans:\n",
    "                ans = dp[i]\n",
    "                ret = f[i]\n",
    "        #print(dp, f, ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums\n",
    "        dp = [[] for _ in range(n)]\n",
    "        res = []\n",
    "        dp[0] = [nums[0]]\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, i):\n",
    "                if dp[j] and nums[i] % dp[j][-1] == 0:\n",
    "                    dp[i] = dp[j] + [nums[i]]\n",
    "                    if len(dp[i]) > len(res):\n",
    "                        res = dp[i]\n",
    "            if not dp[i]:\n",
    "                dp[i].append(nums[i])\n",
    "                if len(dp[i]) > len(res):\n",
    "                    res = dp[i]\n",
    "        print(nums)\n",
    "        print(dp)\n",
    "        return res\n",
    "        # def dfs(index, l):\n",
    "        #     if index >= len(nums):\n",
    "        #         return l\n",
    "        #     if nums[index] == 1 or not l:\n",
    "        #         return dfs(index + 1, l + [nums[index]])\n",
    "        #     else:\n",
    "        #         if nums[index] % l[-1] == 0:\n",
    "        #             t1 = dfs(index + 1, l + [nums[index]])\n",
    "        #             t2 = dfs(index + 1, l)\n",
    "        #             if len(t1) >= len(t2):\n",
    "        #                 t = t1\n",
    "        #             else:\n",
    "        #                 t = t2\n",
    "        #             return t\n",
    "        #         else:\n",
    "        #             t1 = dfs(index + 1, l)\n",
    "        #             t2 = dfs(index + 1, [nums[index]])\n",
    "        #             if len(t1) >= len(t2):\n",
    "        #                 t = t1\n",
    "        #             else:\n",
    "        #                 t = t2\n",
    "        #             return t\n",
    "        #\n",
    "        # res = dfs(0, [])\n",
    "        # # print(res)\n",
    "        # return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        e = defaultdict(list)\n",
    "        ind, pre, d = defaultdict(int), {}, {}\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[i] % nums[j] == 0:\n",
    "                    e[nums[j]].append(nums[i])\n",
    "                    ind[nums[i]] += 1\n",
    "        last = (0, 0)\n",
    "        stack = [x for x in nums if ind[x] == 0]\n",
    "        while stack:\n",
    "            a = stack.pop()\n",
    "            for b in e[a]:\n",
    "                if d.get(b, 0) < d.get(a, 0) + 1:\n",
    "                    d[b] = d.get(a, 0) + 1\n",
    "                    pre[b] = a\n",
    "                    if d[b] > last[0]:\n",
    "                        last = (d[b], b)\n",
    "                ind[b] -= 1\n",
    "                if ind[b] == 0:\n",
    "                    stack.append(b)\n",
    "        if not last[0]:\n",
    "            return [nums[0]]\n",
    "        ans = [last[1]]\n",
    "        while ans[-1] in pre:\n",
    "            ans.append(pre[ans[-1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        answer[i] % answer[j] = 0\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        dp = [1] * n\n",
    "        ans = [set([nums[i]]) for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] % nums[i] == 0:\n",
    "                    if dp[j] < dp[i] + 1:\n",
    "                        dp[j] = dp[i] + 1\n",
    "                        ans[j] = ans[i] | set([nums[j]])\n",
    "        max_val = max(dp)\n",
    "        i = dp.index(max_val)\n",
    "\n",
    "        return list(ans[i])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
